/*
Date:20210519 21:07PM
key:输出数组不算在空间内才有复杂度o
*/
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) 
    {
        int n=nums.size();
        int*left=new int[n];
        
        for(int i=0;i<n;i++)
        {
            if(i==0){left[i]=nums[0];}
            else{
                left[i]=left[i-1]*nums[i];
            }
        }
        int*right=new int[n];
        for(int i=n-1;i>-1;i--)
        {
            if(i==n-1){right[i]=nums[n-1];}
            else{
               right[i]=right[i+1]*nums[i];
            }
        }
        vector<int>v;
        v.resize(n);
        for(int i=0;i<n;i++)
        {
            if(i==0){v[0]=right[1];continue;}
            if(i==n-1){v[n-1]=left[n-2];}
            else
            {
                v[i]=left[i-1]*right[i+1];
            }
        }
        return v;
    }
};